1912

Created at : 2024-02-11 11:45
1912

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> p;
    p.resize(n);
    int m, MaxSum;
    cin >> m;
    p[0] = m;
    MaxSum = m;
    for(int i = 1; i < n; ++i)
    {
        cin >> m;
        p[i] = max(p[i - 1] + m, m);
        MaxSum = max(MaxSum, p[i]);
    }

    cout << MaxSum;

    return 0;
}

어떻게 저 방식으로 DP가 성립하는지 잘 생각해 보아야 한다.

유형

다이나믹 프로그래밍